package leetcode.offer;

import java.util.ArrayList;
import java.util.Arrays;

public class Offer38_Permutation {
    public String[] permutation(String s) {
        ArrayList<String> res = new ArrayList<>();
        if (s.length() == 0 || s.length() == 1) {
            res.add(s);
            return res.toArray(new String[0]);
        }
        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        boolean[] vis = new boolean[s.length()];
        dfs(res, new StringBuilder(), arr, vis);
        return res.toArray(new String[0]);
    }

    public void dfs(ArrayList<String> res, StringBuilder builder, char[] arr, boolean[] vis) {
        if (builder.length() == arr.length) {
            res.add(builder.toString());
        }

        for (int i = 0;i < arr.length;i++) {
            if (vis[i] || (i > 0 && arr[i - 1] == arr[i] && vis[i - 1])) {
                continue;
            }
            vis[i] = true;
            builder.append(arr[i]);
            dfs(res, builder, arr, vis);
            vis[i] = false;
            builder.deleteCharAt(builder.length() - 1);
        }
    }
}
